package LeetCode;

import java.util.Scanner;

import LeetCode.单链表反转.ListNode;

/** 

* @author ：soulstones
* @version ：2019年9月26日 下午9:10:45 
* @Description：
* 

*/
public class 单链表反转 {
	
	public  static class ListNode{
		int data;
		ListNode next;
	}
	
	//非递归方式
	
	public ListNode reverseListNod(ListNode pHead) {
		//反转过后的单链表存储头结点
		ListNode  pReversedHead=null;
		//定义pNode指向pHead
		ListNode pNode = pHead;
		//定义存储前一个结点
		ListNode pPrev=null;
		
		while(pNode !=null) {
			//定义pNext指向pNode的下一个结点
			ListNode pNext = pNode.next;
			
			//如果pNode的下一个结点为空，则pNode即为结果
			if (pNext==null) {
				pReversedHead=pNode;
			}
			//修改pNode指向pNode的下一个结点
			pNode.next=pPrev;
			
			//将pNode结点复制给pPrev
			pPrev=pNode;
			
			//将pNode的下一个结点复制给pNode
			pNode=pNext;
		}
		return pReversedHead;
	}
	
	
	//递归方式实现
	
	public ListNode reverseList2(ListNode pHead) {
		if (pHead==null || pHead.next==null) {
			//如果没有结点或者是只有一个结点则直接返回pHead
			return pHead;
		}
		//保存当前结点的下一个结点
		ListNode pNext = pHead.next;
		//打断当前结点的指针域
		pHead.next=null;
		
		//递归结束时reverseHead一定是新链表的头结点
		ListNode reverseHead = reverseList2(pNext);
		//修改指针域
		pNext.next=pHead;
		return reverseHead;
	}
	


}
